/**
 * 137. 只出现一次的数字 II
 * https://leetcode-cn.com/problems/single-number-ii/submissions/
 */
public class Solutions_137 {
    public static void main(String[] args) {
//        int[] nums = {2, 2, 3, 2};  // output: 3
        int[] nums = {0, 1, 0, 1, 0, 1, 99};  // output: 99

        int result = singleNumber(nums);
        System.out.println(result);
    }

    public static int singleNumber(int[] nums) {
        // bitMap[31] = 4：表示 nums 中全部元素在第 31 位上（从 0 开始，从左往右）有 4 个 bit 位 1
        /**
         * nums = {3, 3, 4, 3}, 4(0b0100), 3(0b0011)
         *  27 28 29 30 31
         *   0  0  1  3  3
         */
        int[] bitMap = new int[32];

        for (int num : nums) {
            // num 可能为负数，故判断条件不用 > 0
            for (int i = 31; i >= 0; i--) {
                bitMap[i] += num & 1;
                num >>= 1;
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            int count = bitMap[i] % 3;
            // count 不为 3 的倍数时，多余的位 1 就是那个只出现一次的数字的一个 bit 1 位
            res += count;
        }
        return res;
    }
}
